home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cocktail / docme.lha / doc.me / highspeed.me < prev    next >
Text File  |  1992-09-25  |  39KB  |  1,293 lines
  1. .\" use: pic | tbl | eqn | ditroff -me
  2. .\"
  3. .\"    "@(#)bibmac.me    2.2    9/9/83";
  4. .de IP
  5. .ip \\$1 \\$2
  6. ..
  7. .de LP
  8. .lp
  9. ..
  10. .\"    @(#)bmac.std    2.2    9/9/83;
  11. .\" standard format troff commands
  12. .\" citation formatting strings
  13. .ds [[ [
  14. .ds ]] ]
  15. .ds ], ,\|
  16. .ds ]- -
  17. .ds [. " \&
  18. .ds .] .
  19. .ds [, " \&
  20. .ds ,] ,
  21. .ds [? " \&
  22. .ds ?] ?
  23. .ds [: " \&
  24. .ds :] :
  25. .ds [; " \&
  26. .ds ;] ;
  27. .ds [! " \&
  28. .ds !] !
  29. .ds [" " \&
  30. .ds "] \&"
  31. .ds [' " \&
  32. .ds '] '
  33. .ds [< " \&
  34. .ds >]
  35. .\" reference formmating strings
  36. .ds a] " \&
  37. .ds b] , \&
  38. .ds c] , \&
  39. .ds n] "\& and \&
  40. .ds m] "\& and \&
  41. .ds p] .
  42. .\" reference formmating macros
  43. .de s[   \" start reference
  44. .nh
  45. .IP [\\*([F] 5m
  46. ..
  47. .de e[   \" end reference
  48. .[-
  49. ..
  50. .de []   \" start to display collected references
  51. .LP
  52. ..
  53. .de ][   \" choose format
  54. .ie !"\\*([J"" \{\
  55. .    ie !"\\*([V"" .nr t[ 1    \" journal
  56. .    el            .nr t[ 5    \" conference paper
  57. .\}
  58. .el .ie !"\\*([B"" .nr t[ 3    \" article in book
  59. .el .ie !"\\*([R"" .nr t[ 4    \" technical report
  60. .el .ie !"\\*([I"" .nr t[ 2    \" book
  61. .el                .nr t[ 0    \" other
  62. .\\n(t[[
  63. ..
  64. .de 0[   \" other
  65. .s[
  66. .if !"\\*([A"" \\*([A\\c
  67. .if !"\\*([T"" , \\*([T\\c
  68. .if !"\\*([V"" , Vol. \\*([V\\c
  69. .if !"\\*([O"" , \\*([O\\c
  70. .if !"\\*([D"" , \\*([D\\c
  71. \&.
  72. .e[
  73. ..
  74. .de 1[ \" journal article
  75. .s[
  76. .if !"\\*([A"" \\*([A,
  77. .if !"\\*([T""  \\*([T,
  78. \\fI\\*([J \\*([V\\fP\c
  79. .if !"\\*([N"" ,\\*([N
  80. .if !"\\*([D"" (\\*([D)\c
  81. .if !"\\*([P"" , \\*([P\c
  82. .if !"\\*([I"" , \\*([I\c
  83. \\&.
  84. .if !"\\*([O"" \\*([O.
  85. .e[
  86. ..
  87. .de 2[ \" book
  88. .s[
  89. .ie !"\\*([A"" \\*([A,
  90. .el .if !"\\*([E"" \{\
  91. .       ie \\n([E-1 \\*([E, eds.,
  92. .       el \\*([E, ed.,\}
  93. .if !"\\*([T"" \\fI\\*([T\\fP,
  94. .rm a[
  95. .if !"\\*([I"" .ds a[ \\*([I
  96. .if !"\\*([C"" \{\
  97. .       if !"\\*(a["" .as a[ , \\&
  98. .       as a[ \\*([C\}
  99. .if !"\\*([D"" \{\
  100. .       if !"\\*(a["" .as a[ , \\&
  101. .       as a[ \\*([D\}
  102. \\*(a[.
  103. .if !"\\*([G"" Gov. ordering no. \\*([G.
  104. .if !"\\*([O"" \\*([O.
  105. .e[
  106. ..
  107. .de 3[ \" article in book
  108. .s[
  109. .if !"\\*([A"" \\*([A,
  110. .if !"\\*([T"" \\*([T,
  111. in \\fI\\*([B\\fP\c
  112. .if !"\\*([V"" , vol. \\*([V
  113. .if !~\\*([E~~ \{\
  114. .       ie , \\n([E-1  \\*([E (editors)\c
  115. .       el , \\*([E (editor)\c\}
  116. .if !"\\*([I"" , \\*([I\c
  117. .if !"\\*([C"" , \\*([C\c
  118. .if !"\\*([D"" , \\*([D\c
  119. .if !"\\*([P"" , \\*([P\c
  120. \\&.
  121. .if !"\\*([O"" \\*([O.
  122. .e[
  123. ..
  124. .de 4[ \" report
  125. .s[
  126. .if !"\\*([A"" \\*([A,
  127. .if !~\\*([E~~ \{\
  128. .       ie \\n([E-1 \\*([E, editors.
  129. .       el \\*([E, editor.\}
  130. \\*([T,
  131. \\*([R\c
  132. .if !"\\*([G"" \& (\\*([G)\c
  133. .if !"\\*([I"" , \\*([I\c
  134. .if !"\\*([C"" , \\*([C\c
  135. .if !"\\*([D"" , \\*([D\c
  136. \\&.
  137. .if !"\\*([O"" \\*([O.
  138. .e[
  139. ..
  140. .de 5[ \" conference paper
  141. .s[
  142. .if !"\\*([A"" \\*([A,
  143. .if !"\\*([T"" \\*([T,
  144. \\fI\\*([J\\fP,
  145. .if !"\\*([C"" \\*([C,
  146. .if !"\\*([D"" \\*([D\c
  147. .if !"\\*([P"" , \\*([P\c
  148. \\&.
  149. .if !"\\*([O"" \\*([O.
  150. .e[
  151. ..
  152. .de [-   \" clean up after yourself
  153. .rm [A [B [C [D
  154. .rm [E [F [G
  155. .rm [I [J [K
  156. .rm [N [O [P
  157. .rm [R [T
  158. .rm [V [W
  159. ..
  160. .\"    @(#)bmac.std    2.2    8/24/83;
  161. .\" standard format troff commands
  162. .\" citation formatting strings
  163. .ds [[ [
  164. .ds ]] ]
  165. .ds ], ,\|
  166. .ds ]- -
  167. .ds [. " \&
  168. .ds .] .
  169. .ds [, " \&
  170. .ds ,] ,
  171. .ds [< " \&
  172. .ds >]
  173. .\" reference formmating strings
  174. .ds c] , \&
  175. .ds n] "" and \&
  176. .ds m] "" and \&
  177. .ds a] " \&
  178. .\" reference formmating macros
  179. .de s[   \" start reference
  180. .nh
  181. .IP [\\*([F] 5m
  182. ..
  183. .de e[   \" end reference
  184. .[-
  185. ..
  186. .de []   \" start to display collected references
  187. .SH
  188. References
  189. .LP
  190. ..
  191. .de ][   \" choose format
  192. .ie !"\\*([J"" \{\
  193. .    ie !"\\*([V"" .nr t[ 1    \" journal
  194. .    el            .nr t[ 5    \" conference paper
  195. .\}
  196. .el .ie !"\\*([B"" .nr t[ 3    \" article in book
  197. .el .ie !"\\*([R"" .nr t[ 4    \" technical report
  198. .el .ie !"\\*([I"" .nr t[ 2    \" book
  199. .el                .nr t[ 0    \" other
  200. .\\n(t[[
  201. ..
  202. .de 0[   \" other
  203. .s[
  204. .if !"\\*([A"" \\*([A,
  205. .if !"\\*([T"" \\*([T,
  206. .if !"\\*([O"" \\*([O\c
  207. .if !"\\*([D"" , \\*([D\c
  208. \&.
  209. .e[
  210. ..
  211. .de 1[ \" journal article
  212. .s[
  213. .if !"\\*([A"" \\*([A,
  214. .if !"\\*([T"" \\*([T,
  215. \\fI\\*([J \\*([V\\fP,
  216. .if !"\\*([N"" \\*([N
  217. .if !"\\*([D"" (\\*([D),
  218. .if !"\\*([P"" \\*([P\c
  219. .if !"\\*([I"" , \\*([I\c
  220. \\&.
  221. .if !"\\*([O"" \\*([O.
  222. .e[
  223. ..
  224. .de 2[ \" book
  225. .s[
  226. .ie !"\\*([A"" \\*([A,
  227. .el .if !"\\*([E"" \{\
  228. .       ie \\n([E-1 \\*([E, eds.,
  229. .       el \\*([E, ed.,\}
  230. .if !"\\*([T"" \\fI\\*([T\\fP,
  231. .rm a[
  232. .if !"\\*([I"" .ds a[ \\*([I
  233. .if !"\\*([C"" \{\
  234. .       if !"\\*(a["" .as a[ , \\&
  235. .       as a[ \\*([C\}
  236. .if !"\\*([D"" \{\
  237. .       if !"\\*(a["" .as a[ , \\&
  238. .       as a[ \\*([D\}
  239. \\*(a[.
  240. .if !"\\*([G"" Gov. ordering no. \\*([G.
  241. .if !"\\*([O"" \\*([O.
  242. .e[
  243. ..
  244. .de 3[ \" article in book
  245. .s[
  246. .if !"\\*([A"" \\*([A,
  247. .if !"\\*([T"" \\*([T,
  248. in \\fI\\*([B\\fP,
  249. .if !"\\*([V"" vol. \\*([V,
  250. .if !"\\*([E"" \\*([E (ed.),
  251. .if !"\\*([I"" \\*([I,
  252. .if !"\\*([C"" \\*([C,
  253. .if !"\\*([D"" \\*([D\c
  254. .if !"\\*([P"" , \\*([P\c
  255. \\&.
  256. .if !"\\*([O"" \\*([O.
  257. .e[
  258. ..
  259. .de 4[ \" report
  260. .s[
  261. .if !"\\*([A"" \\*([A,
  262. \\*([T,
  263. \\*([R\c
  264. .if !"\\*([G"" \& (\\*([G)\c
  265. .if !"\\*([I"" , \\*([I\c
  266. .if !"\\*([C"" , \\*([C\c
  267. .if !"\\*([D"" , \\*([D\c
  268. \\&.
  269. .if !"\\*([O"" , \\*([O.
  270. .e[
  271. ..
  272. .de 5[ \" conference paper
  273. .s[
  274. .if !"\\*([A"" \\*([A,
  275. .if !"\\*([T"" \\*([T,
  276. \\fI\\*([J\\fP,
  277. .if !"\\*([C"" \\*([C\c
  278. .if !"\\*([D"" , \\*([D\c
  279. .if !"\\*([P"" , \\*([P\c
  280. \\&.
  281. .if !"\\*([O"" , \\*([O.
  282. .e[
  283. ..
  284. .de [-   \" clean up after yourself
  285. .rm [A [B [C [D
  286. .rm [E [F [G
  287. .rm [I [J [K
  288. .rm [N [O [P
  289. .rm [R [T
  290. .rm [V [W
  291. ..
  292. .if t \{ \
  293. .pl 29.7c    \" page length
  294. .po 2.5c    \" page offset (left margin)
  295. .ll 16.5c    \" line length
  296. .lt 16.5c    \" title length
  297. .nr LL 16.5c
  298. .nr )l 29.7c
  299. .nr hm 2c
  300. .nr $r 9    \" factor for vertical spacing
  301. .nr $R \n($r
  302. .sz 12        \" font size
  303. .nr pp 12
  304. .nr sp 12
  305. .nr tp 12
  306. .nr fp 10
  307. .hc ~        \" hyphenation character
  308. .        \" Umlauts and sharp s
  309. .ds A \(A:
  310. .ds O \(O:
  311. .ds U \(U:
  312. .ds a \(a:
  313. .ds o \(o:
  314. .ds u \(u:
  315. .ds s \(ss
  316. .        \"  UMLAUT  \*:u, etc.
  317. .ds : \v'-0.6m'\h'(1u-(\\n(.fu%2u))*0.13m+0.06m'\z.\h'0.2m'\z.\h'-((1u-(\\n(.fu%2u))*0.13m+0.26m)'\v'0.6m'
  318. .\}
  319. .if n \{ \
  320. .po 0        \" page offset (left margin)
  321. .ll 78        \" line length
  322. .lt 78        \" title length
  323. .nr $r 4    \" factor for vertical spacing
  324. .nr $R \n($r
  325. .hc ~        \" hyphenation character
  326. .        \" Umlaute und scharfes s
  327. .ds A Ae
  328. .ds O Oe
  329. .ds U Ue
  330. .ds a ae
  331. .ds o oe
  332. .ds u ue
  333. .ds s sz
  334. .\}
  335. .de _
  336. \&\\$1\l'|0\(ul'\\$2
  337. ..
  338. .de FT        \" font for programs
  339. .ft C
  340. .sz -2
  341. ..
  342. .de FR
  343. .ft R
  344. .sz +2
  345. ..
  346. .de []        \" start to display collected references
  347. .uh References
  348. .lp
  349. ..
  350. .de $0        \" collect table of contents
  351. .(x
  352. .ta 2c
  353. .ie '\\$2''    \\$1
  354. .el \\$2.    \\$1
  355. .)x
  356. ..
  357. .de np
  358. .nr $p +1
  359. .ip \\n($p.
  360. ..
  361. .de SH
  362. .sp 0.5
  363. .in -3
  364. .r \\$1
  365. .sp 0.5
  366. .in +3
  367. ..
  368. .de PP
  369. .sp 0.5
  370. ..
  371. .de IP
  372. .ip \\$1 \\$2
  373. ..
  374. .de I
  375. .i \\$1
  376. ..
  377. .de TH
  378. ..
  379. .hc @
  380. .EQ
  381. delim off
  382. .EN
  383. .de FR
  384. .ft R
  385. .sz +2
  386. ..
  387. .b " "
  388. .sp 1c
  389. .ta 9c
  390. .ft R
  391. .sz 12
  392. \l'17.1c'
  393. .nf
  394.  
  395.  
  396.     Generators for
  397.     High-Speed Front-Ends
  398.  
  399.     J. Grosch
  400.  
  401.  
  402. \l'17.1c'
  403. .sp 12.5c
  404. \l'17.1c'
  405. .ft H
  406. .nf
  407.     GESELLSCHAFT F\*UR MATHEMATIK
  408.     UND DATENVERARBEITUNG MBH
  409.  
  410.     FORSCHUNGSSTELLE F\*UR
  411.     PROGRAMMSTRUKTUREN
  412.     AN DER UNIVERSIT\*AT KARLSRUHE
  413. .r
  414. \l'17.1c'
  415. .bp
  416. .oh '''%'
  417. .eh '''%'
  418. .ce 99
  419. .sz 20
  420. .b " "
  421. .sp 2
  422. Project
  423. .sp
  424. .b "Compiler Generation"
  425. .sp
  426. .sz 12
  427. \l'15c'
  428. .sp
  429. .sz 16
  430. .b "Generators for High-Speed Front-Ends"
  431. .sp 2
  432. Josef Grosch
  433. .sp 2
  434. .sz 14
  435. Sept. 28, 1988
  436. .sp
  437. .sz 12
  438. \l'15c'
  439. .sp 2
  440. Report No. 11
  441. .sp 2
  442. Copyright \(co 1988 GMD
  443. .sp 2
  444. Gesellschaft f\*ur Mathematik und Datenverarbeitung mbH
  445. Forschungsstelle an der Universit\*at Karlsruhe
  446. Vincenz-Prie\*snitz-Str. 1
  447. D-7500 Karlsruhe
  448. .ce 0
  449. .fi
  450. .bp 2
  451. .ce 99
  452. .b
  453. Generators for High-Speed Front-Ends
  454. .sp 2
  455. .r
  456. Josef Grosch
  457. GMD Forschungsstelle f\*ur Programmstrukturen an der Universit\*at Karlsruhe
  458. Vincenz-Prie\*snitz-Str. 1, D-7500 Karlsruhe 1, West Germany
  459. .sp 2
  460. .ce 0
  461. .uh Abstract
  462. .pp
  463. High-speed compilers can be constructed automatically. We present some
  464. existing tools for the generation of fast front-ends.
  465. .\" High-speed compilers can be constructed automatically. We present some
  466. .\" existing tools for the generation of front-ends and describe our current
  467. .\" work on future tools.
  468. .pp
  469. .i Rex
  470. (Regular EXpression tool) is a scanner generator whose specifications are
  471. based on regular expressions and arbitrary semantic actions written in one
  472. of the target languages C or Modula-2. As scanners sometimes have to
  473. consider the context to unambiguously recognize a token the right context
  474. can be specified by an additional regular expression and the left context
  475. can be handled by so-called start states. The generated scanners
  476. automatically compute the line and column position of the tokens and offer
  477. an efficient mechanism to normalize identifiers and keywords to upper or
  478. lower case letters. The scanners are table-driven and run at a speed of
  479. 180,000 to 195,000 lines per minute on a MC 68020 processor.
  480. .pp
  481. .i Lalr
  482. is a LALR(1) parser generator accepting grammars written in extended BNF
  483. notation which may be augmented by semantic actions expressed by statements
  484. of the target language. The generator provides a mechanism for
  485. S-attribution, that is synthesized attributes can be computed during
  486. parsing. In case of LR-conflicts, unlike other tools,
  487. .i Lalr
  488. provides not only information about an internal state consisting of a set of
  489. items but it prints a derivation tree which is much more useful to analyze
  490. the problem. Conflicts can be resolved by specifying precedence and
  491. associativity of operators and productions. The generated parsers include
  492. automatic error reporting, error recovery, and error repair. The parsers are
  493. table-driven and run at a speed of 580,000 lines per minute. Currently
  494. parsers can be generated in the target languages C and Modula-2.
  495. .pp
  496. .i Ell
  497. is a LL(1) parser generator accepting the same specification language as
  498. .i Lalr
  499. except that the grammars must obey the LL(1) property. The generated parsers
  500. include automatic error reporting, recovery, and repair like
  501. \fILalr\fP.
  502. The parsers are implemented following the recursive descent method and reach
  503. a speed of 900,000 lines per minute. The possible target languages are again
  504. C and Modula-2.
  505. .pp
  506. A comparison of the above tools with the corresponding UNIX tools shows
  507. that significant improvements have been achieved thus allowing
  508. the generation of high-speed compilers.
  509. .\" .pp
  510. .\" Currently we are working on tools for semantic analysis and transformation.
  511. .\" Semantic analysis will be based on attribute grammars. We are trying to
  512. .\" structure semantic analysis into separate, probably reusable modules and to
  513. .\" combine this with an efficient way to perform attribute evaluation. The
  514. .\" transformation phase maps an attributed tree to an intermediate
  515. .\" language. This phase can be specified by a tree mapping and it can be
  516. .\" implemented efficiently based on pattern matching.
  517. .sh 1 "The Scanner Generator Rex"
  518. .pp
  519. The scanner generator \fIRex\fP has been developed with the aim to combine
  520. the powerful specification method of regular expressions with the generation
  521. of highly efficient scanners. The name \fIRex\fP stands for
  522. .i "regular expression tool,"
  523. reflecting the specification method.
  524. .pp
  525. A scanner specification consists in principle of a set of regular
  526. expressions each associated with a semantic action. Whenever a string
  527. constructed according to a regular expression is recognized in the input of
  528. the scanner its semantic action which is a sequence of arbitrary statements
  529. written in the target language is executed. To be able to recognize tokens
  530. depending on their context \fIRex\fP provides start states to handle left context
  531. and the right context can be specified by an additional regular expression.
  532. If several regular expressions match the input characters, the
  533. longest match is preferred. If there are still several possibilities, the
  534. regular expression given first in the specification is chosen.
  535. .pp
  536. \fIRex\fP generated scanners automatically provide the line and column position of
  537. each token. For languages like Pascal and Ada where the case of letters is
  538. insignificant tokens can be normalized to lower or upper case. There are
  539. predefined rules to skip white space like blanks, tabs, or newlines.
  540. .pp
  541. The generated scanners are table-driven deterministic finite automatons. The
  542. tables are compressed using the so-called comb-vector technique
  543. \*([[ASU86\*(]]. Whereas the generator \fIRex\fP is implemented in Modula-2
  544. it can generate scanners in the languages C and Modula-2. Currently \fIRex\fP is
  545. available for PCS Cadmus/UNIX and SUN/UNIX workstations.
  546. .pp
  547. The most outstanding feature of \fIRex\fP is its speed. The generated scanners
  548. process nearly 200,000 lines per minute without hashing of identifiers and
  549. up to 150,000 lines per minute if hashing is applied. This is 4 times the
  550. speed of \fILex\fP\*([<\*([[Les75\*(]]\*(>] generated scanners. In typical cases \fIRex\fP generated
  551. scanners are 4 times smaller then \fILex\fP generated ones (around 15 KB). Usually
  552. \fIRex\fP takes only 1/10 of the time of \fILex\fP to generate a scanner. All figures
  553. have been measured on a MC 68020 processor.
  554. .pp
  555. In the following we will demonstrate the powerful specification method
  556. provided by \fIRex\fP and present a comparison with other scanner generators.
  557. .sh 2 "Structure of Specification"
  558. .(z I
  559. .FT
  560. EXPORT  { external declarations }
  561. GLOBAL  { global   declarations }
  562. LOCAL   { local    declarations }
  563. BEGIN   { initialization code   }
  564. CLOSE   { finalization   code   }
  565. DEFAULT { default action        }
  566. EOF     { end of file action    }
  567. DEFINE    definition of regular expressions
  568. START     definition of start states
  569. RULE      regular expressions and semantic actions
  570.  
  571. .FR
  572. Fig. 1: Structure of Specification
  573. .)z
  574. .pp
  575. A complete scanner specification is structured like shown in Figure 1. The
  576. regular expressions may be preceded by six sections containing arbitrary
  577. target code, which may contain declarations to be used in the semantic
  578. actions or statements for initialization and finalization of data
  579. structures. The DEFINE and START sections serve to abbreviate regular
  580. expressions by identifiers and to declare start states (see below).
  581. A complete definition of the specification language can be found in the user
  582. manual\*([<\*([[Gro87\*(]]\*(>].
  583. .sh 2 "Right Context"
  584. .pp
  585. There are languages where the strategy of the longest match fails. For
  586. example in Modula-2 the input \fC1..\fP has to be recognized as
  587. tokens "\fC1\fP" and "\fP..\fP", not as "\fC1.\fP" and "\fP.\fP",
  588. which are also two legal Modula tokens.
  589. The problem can be solved using an additional regular expression to describe
  590. this situation where the right context of a token leads to an exception in
  591. the longest match strategy. Figure 2 shows the syntax used in \fIRex\fP for
  592. regular expressions and semantic actions to describe the 4 tokens involved
  593. in the above problem. The character '/' separating two regular expressions
  594. specifies to recognize a sequence of digits only if it is followed
  595. by two dots.
  596. .(b I
  597. .sp 0.5
  598. .FT
  599. {0-9} +             : { return SymDecimal; }
  600. {0-9} + / ".."      : { return SymDecimal; }
  601. {0-9} + "." {0-9} * : { return SymReal   ; }
  602. ".."                : { return SymRange  ; }
  603. "."                 : { return SymDot    ; }
  604.  
  605. .FR
  606. Fig. 2: Scanner Specification Using Right Context
  607. .)b
  608. .sh 2 "Start States"
  609. .(z I
  610. .FT
  611. GLOBAL  {VAR NestingLevel: CARDINAL;}
  612. .sp 0.5
  613. BEGIN   {NestingLevel := 0;}
  614. .sp 0.5
  615. EOF     {IF yyStartState = Comment THEN Error ("unclosed comment"); END;}
  616. .sp 0.5
  617. DEFINE  CmtCh   = - {*(\\\\t\\\\n}.
  618. .sp 0.5
  619. START   Comment
  620. .sp 0.5
  621. RULES
  622.            "(*" : {INC (NestingLevel); yyStart (Comment);}
  623. .sp 0.5
  624. #Comment#  "*)" : {DEC (NestingLevel);
  625.                    IF NestingLevel = 0 THEN yyStart (STD); END;}
  626. .sp 0.5
  627. #Comment#  "(" | "*" | CmtCh + : {}
  628.  
  629. .FR
  630. Fig. 3: Scanner Specification Using Start States
  631. .)z
  632. .pp
  633. To handle tokens whose recognition depends on the left context or to process
  634. even tokens which cannot be specified by regular expressions the scanners
  635. can have several start states. In every start state a different set of
  636. regular expressions is recognized. There is a special statement to change
  637. the current start state (yyStart). For example nested comments like in
  638. Modula can be scanned as shown in Figure 3.
  639. .sh 2 "Ada Quote Problem"
  640. .pp
  641. The Ada quote problem can also be solved using start states. The problem is
  642. to scan for example
  643. .(b
  644. .FT
  645. t'(',',',',',') \fP as \fP
  646. t    '    (    ','    ,    ','    ,    ','    ) \fP and not as \fP
  647. t    '('    ,    ','    ,    ','    ,    '    )
  648. .)b
  649. which are both possible sequences of Ada tokens. The correct solution again
  650. violates the longest match strategy. A careful study of the language
  651. definition reveals that single quotes only appear behind identifiers and
  652. closing parentheses. Figure 4 shows the structure of a solution.
  653. After recognizing one of these two tokens we switch to start state QUOTE
  654. which recognizes among other tokens single quotes. After all the other
  655. tokens we switch to the predefined start state STD where quotes are only
  656. accepted as delimiters for character literals.
  657. More examples of scanner specifications can be found in\*([<\*([[Gro88\*(]]\*(>].
  658. .(b I
  659. .sp 0.5
  660. .FT
  661. .\" EXPORT  {
  662. .\" # include "SymbolTable.h"
  663. .\" typedef union {char vChar; tSymbol vSymbol} tAttribute;
  664. .\" extern void ErrorAttribute (); }
  665. .\" 
  666. .\" GLOBAL  {
  667. .\" void ErrorAttribute (Symbol, Attribute) ...  }
  668. .\" 
  669. LOCAL   {char  Word [256]; int   L;}
  670. .sp 0.5
  671. DEFINE  character = {\\\\ -~}.
  672.         letter    = {A-Z a-z}.
  673.         digit     = {0-9}.
  674. .sp 0.5
  675. START   QUOTE
  676. .sp 0.5
  677. RULES
  678. .sp 0.5
  679. #STD# ' character ' : {
  680.       L = GetWord (Word);
  681.       Attribute.vChar = Word [1];
  682.       return SymCharacterLiteral;}
  683. .sp 0.5
  684. #QUOTE# ' : {
  685.       yyStart (STD);
  686.       return SymApostrophe;}
  687. .sp 0.5
  688. "(" : {yyStart (STD); return SymLParenthesis;}
  689. .sp 0.5
  690. ")" : {yyStart (QUOTE); return SymRParenthesis;}
  691. .sp 0.5
  692. letter (_? (letter | digit)+ )* : {
  693.       yyStart (QUOTE); L = GetLower (Word);
  694.       Attribute.vSymbol = MakeSymbol (Word, L);
  695.       return SymIdentifier;}
  696.  
  697. .FR
  698. Fig. 4: Scanner Specification Solving the Ada Quote Problem
  699. .)b
  700. .sh 2 "Comparison of Scanner Generators"
  701. .(z
  702. .TS
  703. tab (;) box center;
  704. l | l l l
  705. l | l l l.
  706.                   ;Lex    ;Flex   ;Rex
  707. _
  708. specification     ;regular;regular;regular
  709.    language       ;  expressions;  expressions;  expressions
  710. semantic actions  ;yes    ;yes    ;yes
  711. right context     ;yes    ;yes    ;yes
  712. start states      ;yes    ;yes    ;yes
  713. _
  714. conflict solution ;longest match;longest match;longest match
  715.                   ;first rule   ;first rule   ;first rule
  716. _
  717. source coordinates;line   ;-      ;line + column
  718. case normalization;-      ;yes    ;yes
  719. predefined rules to;-     ;-      ;yes
  720.    skip white space
  721. several solutions ;yes    ;yes    ;-
  722.    (REJECT)
  723. adjustment of     ;by hand;automatic;automatic
  724.    internal arrays
  725. _
  726. scanning method   ;table-driven ;table-driven ;table-driven
  727. table compression ;comb-vector  ;comb-vector  ;comb-vector 
  728. _
  729. implementation    ;C      ;C      ;C, Modula
  730.    languages
  731. target languages  ;C      ;C      ;C, Modula
  732. _
  733. speed [lines/min.]
  734.    without hashing;36,400 ;139,000;182,700
  735.    with hashing   ;34,700 ;118,000;141,400
  736. _
  737. table size [bytes];39,200 ;57,300 ;4,400
  738. scanner size [bytes];43,800 ;64,100 ;11,200
  739. _
  740. generation time [sec.];73.7;7.2   ;4.9
  741. .TE
  742.  
  743. .ce
  744. Fig. 5: Comparison of Scanner Generators (speed measured on MC 68020 processor)
  745. .)z
  746. .pp
  747. Figure 5 compares \fIRex\fP to the classical UNIX scanner generator \fILex\fP\*([<\*([[Les75\*(]]\*(>]
  748. and to the new public domain remake of \fILex\fP called \fIFlex\fP\*([<\*([[Pax88\*(]]\*(>]
  749. (for fast \fILex\fP). The table
  750. compares the specification technique and the performance of the generators
  751. as well as of the generated scanners. The specification dependent numbers
  752. for generation time and scanner size are for a Modula-2 scanner.
  753. .sh 1 "The Parser Generator Lalr"
  754. .pp
  755. The parser generator \fILalr\fP has been developed with the aim to combine a
  756. powerful specification technique for context-free languages with the
  757. generation of highly efficient parsers. As it processes the class of LALR(1)
  758. grammars we chose the name \fILalr\fP to express the power of the specification
  759. technique.
  760. .pp
  761. The grammars may be written using extended BNF constructs. Each grammar rule
  762. may be associated with a semantic action consisting of arbitrary statements
  763. written in the target language. Whenever a grammar rule is recognized by the
  764. generated parser the associated semantic action is executed. A mechanism for
  765. S-attribution (only synthesized attributes) is provided to allow
  766. communication between the semantic actions.
  767. .pp
  768. In case of LR-conflicts a derivation tree is printed to ease in locating the
  769. problem. The conflict can be resolved by specifying precedence and
  770. associativity for terminals and rules. Syntactic errors are handled fully
  771. automatically by the generated parsers including error reporting, recovery,
  772. and repair. The mentioned features are discussed in more detail in the
  773. following chapters.
  774. .pp
  775. The generated parsers are table-driven. Like in the case of \fIRex\fP comb-vector
  776. technique is used to compress the parse tables. The generator \fILalr\fP is
  777. implemented in the language Modula-2. Parsers can be generated in the
  778. languages C and Modula-2. The generator uses the algorithm described by
  779. \*([[DeP82\*(]] to compute the look-ahead sets although the
  780. algorithm published by\*([<\*([[Ive86\*(]]\*(>] promises to perform better. Currently \fILalr\fP is
  781. available for PCS-Cadmus/UNIX and SUN/UNIX workstations.
  782. .pp
  783. Parsers generated by \fILalr\fP are twice as fast as \fIYacc\fP\*([<\*([[Joh75\*(]]\*(>] generated
  784. ones. They reach a speed of 580,000 lines per minute on a MC 68020 processor
  785. excluding the time for scanning. The size of the parsers is only slightly
  786. increased in comparison to \fIYacc\fP (e. g. 37 KB for Ada), because there
  787. is a small price to be paid for the speed.
  788. .pp
  789. In the following we will discuss some features of \fILalr\fP in detail and
  790. present a comparison to other parser generators.
  791. Further information about the implementation
  792. of \fILalr\fP can be found in\*([<\*([[Gro90\*(]]\*(>].
  793. .sh 2 "Structure of Specification"
  794. .(z I
  795. .FT
  796. EXPORT { external declarations }
  797. GLOBAL { global   declarations }
  798. LOCAL  { local    declarations }
  799. BEGIN  { initialization code   }
  800. CLOSE  { finalization   code   }
  801. TOKEN    coding of terminals
  802. OPER     precedence of operators
  803. RULE     grammar rules and semantic actions
  804.  
  805. .FR
  806. Fig. 6: Structure of Specification
  807. .)z
  808. .pp
  809. The structure of a parser specification follows the style of a \fIRex\fP
  810. specification as shown in Figure 6. Again, there may be five sections to
  811. include target code. The TOKEN section defines the terminals of the grammar
  812. and their encoding. In the OPER (for operator) section precedence and
  813. associativity for terminals can be specified to resolve LR-conflicts. The
  814. RULE section contains the grammar rules and semantic actions.
  815. A complete definition of the specification language can be found in the user
  816. manual\*([<\*([[GrV88\*(]]\*(>].
  817. .sh 2 "S-Attribution"
  818. .pp
  819. Figure 7 shows an example for the syntax of grammar rules and semantic
  820. actions. The semantic actions may access and evaluate attributes associated
  821. with the nonterminals and terminals of the grammar rules. This attributes
  822. are currently denoted in the less readable "numeric" style of \fIYacc\fP\*([<\*([[Joh75\*(]]\*(>].
  823. .(b I
  824. .sp 0.5
  825. .FT
  826. expr : expr '+' expr { $0.value := $1.value + $3.value; } .
  827. expr : expr '*' expr { $0.value := $1.value * $3.value; } .
  828. expr : '(' expr ')'  { $0.value := $2.value; } .
  829. expr : number        { $0.value := $1.value; } .
  830.  
  831. .FR
  832. Fig. 7: Grammar Rules Using S-Attribution
  833. .)b
  834. .sh 2 "Ambiguous Grammars"
  835. .pp
  836. The grammar of Figure 7 as well as the example in Figure 8 are typical
  837. examples of ambiguous grammars. Like \fIYacc\fP we allow to resolve the resulting
  838. LR-conflicts
  839. by specifying precedence and associativity for terminals in the OPER
  840. section. Figure 9 gives an example. The lines represent increasing levels of
  841. precedence. LEFT, RIGHT, and NONE denote left-associativity,
  842. right-associativity, and no associativity. Rules can inherit the properties
  843. of a terminal with the PREC suffix.
  844. .(b I
  845. .sp 0.5
  846. .FT
  847. stmt : 'IF' expr 'THEN' stmt               PREC LOW
  848.      | 'IF' expr 'THEN' stmt 'ELSE' stmt   PREC HIGH .
  849.  
  850. .FR
  851. Fig. 8: Ambiguous Grammar (Dangling Else)
  852. .)b
  853. .(b I
  854. .FT
  855. OPER  LEFT '+'
  856.       LEFT '*'
  857.       NONE LOW
  858.       NONE HIGH
  859.  
  860. .FR
  861. Fig. 9: Resolution of LR-Conflicts Using Precedence and Associativity
  862. .)b
  863. .sh 2 "LR-Conflict Message"
  864. .(z I
  865. .FT
  866. State 266
  867.  
  868. read reduce conflict
  869.  
  870. \&program End-of-Tokens 
  871. \&'PROGRAM' identifier params ';' block '.' 
  872. \&................................:
  873. \&:
  874. \&labels consts types vars procs 'BEGIN' stmts 'END' 
  875. \&.......................................:
  876. \&:
  877. \&stmt 
  878. \&'IF' expr 'THEN' stmt 'ELSE' stmt 
  879.                  :
  880.                  'IF' expr 'THEN' stmt 
  881.                  :
  882. reduce   stmt -> 'IF' expr 'THEN' stmt.  {'ELSE'}  ?
  883. read     stmt -> 'IF' expr 'THEN' stmt.'ELSE' stmt  ?
  884.  
  885. .FR
  886. Fig. 10: Derivation Tree for an LR-Conflict (Dangling Else)
  887. .)z
  888. .pp
  889. To ease in locating the reason for LR-conflicts we adopted the method
  890. proposed by\*([<\*([[DeP82\*(]]\*(>]. Besides reporting the type of
  891. the conflict and the involved items (whatever that is for the user) like most
  892. LR parser generators do, additionally a derivation tree is printed.
  893. Figure 10 shows an
  894. example. It shows how the items and the look-ahead tokens get into the
  895. conflict situation. In general there can be two trees if the derivations for
  896. the conflicting items are different. Each tree consists of 3 parts. An
  897. initial part begins at the start symbol of the grammar. At a certain node
  898. (rule) two subtrees explain the emergence of the item and the look-ahead.
  899. .pp
  900. Every line contains a right-hand side of a grammar rule. Usually the
  901. right-hand side is indented to start below the nonterminal of the left-hand
  902. side. To avoid line overflow dotted edges also refer to the left-hand side
  903. nonterminal and allow to shift back to the left margin. In Figure 10 the
  904. initial tree part consists of 5 lines (not counting the dotted lines). The
  905. symbols 'stmt' and 'ELSE' are the roots of the other two tree parts. This
  906. location is indicated by the "unnecessary" colon in the following line.
  907. After one intermediate line the left subtree derives the conflicting items.
  908. The right subtree consists in this case only of the root node (the terminal
  909. \&'ELSE') indicating the look-ahead. In general this can be a tree of
  910. arbitrary size. The LR-conflict can easily be seen from this tree fragment.
  911. If conditional statements are nested like shown there is a read reduce
  912. conflict (also called shift reduce conflict).
  913. .sh 2 "Error Recovery"
  914. .(z I
  915. Source Program:
  916. .sp 0.5
  917. .FT
  918. program test (output);
  919. begin
  920.    if (a = b] write (a);
  921. end.
  922. .sp 0.5
  923. .FR
  924. Error Messages:
  925. .sp 0.5
  926. .FT
  927. 3, 13: Error       syntax error     
  928. 3, 13: Information expected symbols: ')' '*' '+' '-' '/' '<' '<='
  929.                    '=' '<>' '>' '>=' 'AND' 'DIV' 'IN' 'MOD' 'OR'
  930. 3, 15: Information restart point    
  931. 3, 15: Repair      symbol inserted : ')'
  932. 3, 15: Repair      symbol inserted : 'THEN'
  933.  
  934. .FR
  935. Fig. 11: Example of Automatic Error Messages
  936. .)z
  937. .pp
  938. The generated parsers include information and algorithms to handle syntax
  939. errors completely automatically. We follow the complete backtrack-free
  940. method described by
  941. \*([[R\*oh76\*(],R\*oh80\*(],R\*oh82\*(]]
  942. and provide expressive reporting, recovery, and repair. Every incorrect input
  943. is "virtually" transformed into a syntactically correct program with the
  944. consequence of only executing a "correct" sequence of semantic actions.
  945. Therefore the following compiler phases like semantic analysis don't have to
  946. bother with syntax errors. \fILalr\fP provides a prototype error module which
  947. prints messages as shown in Figure 11.
  948. Internally the error recovery works as follows:
  949. .ip - 0.5c
  950. The location of the syntax error is reported.
  951. .ip - 0.5c
  952. All the tokens that would be a legal continuation of the program are
  953. computed and reported.
  954. .ip - 0.5c
  955. All the tokens that can serve to continue parsing are computed. A minimal
  956. sequence of tokens is skipped until one of these tokens is found.
  957. .ip - 0.5c
  958. The recovery location is reported.
  959. .ip - 0.5c
  960. Parsing continues in the so-called repair mode. In this mode the parser
  961. behaves as usual except that no tokens are read from the input. Instead a
  962. minimal sequence of tokens is synthesized to repair the error.
  963. The parser stays in this mode until the input token can be accepted.
  964. The synthesized tokens are reported. The program can be regarded as
  965. repaired, if the skipped tokens are replaced by the synthesized ones.
  966. With leaving the repair mode parsing continues as usual.
  967. .sh 2 "Comparison of Parser Generators"
  968. .(z
  969. .TS
  970. tab (;) box center;
  971. l1 |1 l1 l1 l1 l1 l
  972. l1 |1 l1 l1 l1 l1 l.
  973.                  ;Bison  ;Yacc   ;PGS    ;Lalr   ;Ell
  974. _
  975. spec. language   ;BNF    ;BNF    ;EBNF   ;EBNF   ;EBNF
  976. grammar class    ;LALR(1);LALR(1);LALR(1);LALR(1);LL(1)
  977.                  ;       ;       ;LR(1)  ;       ;
  978.                  ;       ;       ;SLR(1) ;       ;
  979. semantic actions ;yes    ;yes    ;yes    ;yes    ;yes
  980. S-attribution    ;numeric;numeric;symbolic;numeric;-
  981. L-attribution    ;-      ;-      ;-      ;-      ;planned
  982. _
  983. conflict message ;state, ;state, ;state, ;derivation-;-
  984.                  ;  items;  items;  items;  tree ;
  985. conflict solution;precedence;precedence;modification;precedence;
  986.                  ;associativity;associativity; ;associativity;
  987. chain rule elim. ;-      ;-      ;yes    ;-      ;-
  988. error recovery   ;by hand;by hand;automatic;automatic;automatic
  989. error repair     ;-      ;-      ;yes    ;yes    ;yes
  990. _
  991. parsing method   ;table-driven;table-driven;table-driven;table-driven;recursive
  992.                  ;       ;       ;       ;       ;  descent
  993. table compression;comb-vector;comb-vector;comb-vector;comb-vector;-
  994. _
  995. impl. language   ;C      ;C      ;Pascal ;Modula ; Modula
  996. target languages ;C      ;C      ;C      ;C      ;C
  997.                  ;       ;       ;Modula ;Modula ;Modula
  998.                  ;       ;       ;Pascal
  999.                  ;       ;       ;Ada
  1000. _
  1001. speed [tokens/sec.];9,000;16,000;17,300;35,000;54,600
  1002. speed [lines/min.];150,000;270,000;290,000;580,000;900,000
  1003. _
  1004. table size [bytes] ;8,004;10,364 ;11,268 ;11,795 ;-
  1005. parser size [bytes];11,136;12,548 ;17,616 ;17,416 ;14,344
  1006. _
  1007. gen. time [sec.] ;5.0    ;19.6   ;69.5   ;29.6   ;6.4
  1008. _
  1009. availability     ;UNIX   ;UNIX   ;PCS/UNIX;PCS/UNIX;PCS/UNIX
  1010.                  ;       ;       ;VAX/UNIX;SUN/UNIX;SUN/UNIX
  1011.                  ;       ;       ;  BSD 4.2
  1012.                  ;       ;       ;SIEMENS/
  1013.                  ;       ;       ;  BS2000
  1014. .TE
  1015.  
  1016. .ce
  1017. Fig. 12: Comparison of Parser Generators (speed measured on a MC 68020 processor)
  1018. .)z
  1019. .pp
  1020. Figure 12 compares \fILalr\fP with:
  1021. .ta 1.5c
  1022. .ip - 0.5c
  1023. Yacc    well known from UNIX\*([<\*([[Joh75\*(]]\*(>]
  1024. .ip - 0.5c
  1025. Bison    public domain remake of \fIYacc\fP\*([<\*([[GNU88\*(]]\*(>]
  1026. .ip - 0.5c
  1027. PGS    Parser Generating System also developed at Karlsruhe\*([<\*([[GrK86\*(],KlM89\*(]]\*(>]
  1028. .ip - 0.5c
  1029. Ell    recursive descent parser generator described in chapter 3.
  1030. .pp
  1031. The language dependent numbers exclude time and size for scanning and refer
  1032. to experiments with a Modula-2 parser.
  1033. .pp
  1034. The measurements of the parser speed turned out to be a hairy business.
  1035. The results can be influenced in many ways from:
  1036. .ip - 0.5c
  1037. The hardware: We used a PCS Cadmus 9900 with a MC68020 processor running
  1038. at a clock rate of 20 MHz.
  1039. .ip - 0.5c
  1040. The compiler: We used the C compiler of PCS.
  1041. .ip - 0.5c
  1042. The language: We used Modula-2.
  1043. .ip - 0.5c
  1044. The size of the language: In the case of \fILalr\fP the size of the
  1045. language or the size of the grammar does not influence the speed of the
  1046. parser because the same table-driven algorithm and the same data structure
  1047. is used in every case. This can be different for other parsers. For example
  1048. the speed of directly coded parsers decreases with an increasing grammar
  1049. size.  PGS stores states in one byte if there are less than 256 states and in
  1050. two bytes otherwise. This increases the speed for small grammars, too,
  1051. at least on byte-addressable machines.
  1052. .ip - 0.5c
  1053. The grammar style, the number of rules, especially chain rules and the
  1054. like: We used the same grammar for most experiments which had as few chain
  1055. rules as possible and which caused as few reduce actions as possible. This
  1056. means e. g. we specified expressions in an ambiguous style like shown in
  1057. Figure 7. Exceptions are \fIEll\fP which needs an LL(1) grammar and PGS, because
  1058. modifications are inelegant to resolve many ambiguities.
  1059. .ip - 0.5c
  1060. The test input: We used the same large Modula program as test data in
  1061. every case, of course.
  1062. Nevertheless the programming style or the code "density" influence the
  1063. resulting speed. This effect could be eliminated by selecting tokens per
  1064. minute as measure. In spite of this we chose lines per minute as measure
  1065. because we find this to be more expressive.
  1066. (In the average there are 4 tokens in a line).
  1067. .ip - 0.5c
  1068. The timing: We measured CPU-time and subtracted the total time and the
  1069. scanner time to get the parser time.
  1070. .ip - 0.5c
  1071. The semantic actions: We specified empty semantic actions for all rules in
  1072. order to simulate the conditions in a realistic application. This has more
  1073. consequences as one might think. It disables a short cut of \fIYacc\fP and the
  1074. chain rule elimination\*([<\*([[WaG84\*(]]\*(>] of PGS,
  1075. decreasing the speed in both cases. A further
  1076. experiment with PGS revealed even more problems. To allow chain rule
  1077. elimination we deleted the empty semantic actions for chain rules.
  1078. Surprisingly, instead of getting faster the parser was slower. The reason is
  1079. that chain rule elimination increases the number of states. Accidentally we
  1080. exceeded the number of 256. Now states have to be stored in two bytes instead
  1081. of one. The additional memory accesses are more expensive than the win from
  1082. the chain rule elimination.
  1083. .sh 1 "The Parser Generator Ell"
  1084. .pp
  1085. The parser generator \fIEll\fP processes LL(1) grammars which may contain extended
  1086. BNF constructs and semantic actions and generates a recursive descent
  1087. parser. A mechanism for L-attribution (inherited and synthesized attributes
  1088. evaluable during one preorder traversal) is to be added. Like \fILalr\fP syntax
  1089. errors are handled fully automatic including error reporting from a prototype
  1090. error module, error recovery, and error repair. The generator \fIEll\fP is
  1091. implemented in Modula-2 and can generate parsers in C and Modula-2. Those
  1092. satisfied with the restricted power of LL(1) grammars may profit from the
  1093. high speed of the generated parsers which lies around 900,000 lines per
  1094. minute. For a detailed comparison see Figure 12.
  1095. .sh 1 "Conclusion"
  1096. .pp
  1097. We presented the tools \fIRex\fP, \fILalr\fP, and \fIEll\fP that allow the
  1098. generation of
  1099. efficient compiler front-ends. The combination of generated scanners and
  1100. parsers reach speeds of more than 100,000 lines per minute or almost
  1101. 2,000 lines per second. As scanning itself is one of the dominating tasks in
  1102. a compiler we belief that compilers with a total performance of 1,000 lines
  1103. per second can be generated automatically. Our current work concentrates on
  1104. tools for semantic analysis based on attribute grammars and code generation
  1105. based on pattern matching.
  1106. .uh Acknowledgements
  1107. .pp
  1108. The author implemented \fIRex\fP and contributed the parser skeletons in C
  1109. and Modula-2 for \fILalr\fP. The generator program \fILalr\fP was written
  1110. and debugged by Bertram Vielsack who also 
  1111. provided the experimental results for the parser generators.
  1112. The parser generator \fIEll\fP was programmed by Doris Kuske.
  1113. .fi
  1114. .sz 12
  1115. .[]
  1116. .[-
  1117. .ds [F ASU86
  1118. .ds [A A\*(p]\*(a]V\*(p] Aho
  1119. .as [A \*(c]R\*(p] Sethi
  1120. .as [A \*(m]J\*(p]\*(a]D\*(p] Ullman
  1121. .ds [T Compilers: Principles, Techniques, and Tools
  1122. .ds [I Addison Wesley
  1123. .ds [C Reading, M\&A
  1124. .ds [D 1986
  1125. .][
  1126. .[-
  1127. .ds [F DeP82
  1128. .ds [A F\*(p] DeRemer
  1129. .as [A \*(n]T\*(p] Pennello
  1130. .ds [T Efficient Computation of LALR(1) Look-Ahead Sets
  1131. .nr [P 1
  1132. .ds [P 615-649
  1133. .ds [J ACM Trans. Prog. Lang. and Systems
  1134. .ds [V 4
  1135. .ds [N 4
  1136. .ds [D Oct. 1982
  1137. .][
  1138. .[-
  1139. .ds [F GNU88
  1140. .ds [A GNU\ Project
  1141. .ds [T Bison - Manual Page
  1142. .ds [I Public Domain Software
  1143. .ds [D 1988
  1144. .][
  1145. .[-
  1146. .ds [F GrK86
  1147. .ds [A J\*(p] Grosch
  1148. .as [A \*(n]E\*(p] Klein
  1149. .ds [T User Manual for the PGS-System
  1150. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1151. .ds [D Aug. 1986
  1152. .][
  1153. .[-
  1154. .ds [F Gro87
  1155. .ds [A J\*(p] Grosch
  1156. .ds [T Rex - A Scanner Generator
  1157. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1158. .ds [R Compiler Generation Report No. 5
  1159. .ds [N 5
  1160. .ds [D Dec. 1987
  1161. .][
  1162. .[-
  1163. .ds [F Gro88
  1164. .ds [A J\*(p] Grosch
  1165. .ds [T Selected Examples of Scanner Specifications
  1166. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1167. .ds [R Compiler Generation Report No. 7
  1168. .ds [N 7
  1169. .ds [D Mar. 1988
  1170. .][
  1171. .[-
  1172. .ds [F GrV88
  1173. .ds [A J\*(p] Grosch
  1174. .as [A \*(n]B\*(p] Vielsack
  1175. .ds [T The Parser Generators Lalr and Ell
  1176. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1177. .ds [R Compiler Generation Report No. 8
  1178. .ds [N 8
  1179. .ds [D Apr. 1988
  1180. .][
  1181. .[-
  1182. .ds [F Gro90
  1183. .ds [A J\*(p] Grosch
  1184. .ds [T Lalr - a Generator for Efficient Parsers
  1185. .ds [J Software\(emPractice & Experience
  1186. .ds [V 20
  1187. .ds [N 11
  1188. .ds [D Nov. 1990
  1189. .nr [P 1
  1190. .ds [P 1115-1135
  1191. .][
  1192. .[-
  1193. .ds [F Ive86
  1194. .ds [A F\*(p] Ives
  1195. .ds [T Unifying View of Recent LALR(1) Lookahead Set Algorithms
  1196. .ds [J SI\&GPLAN Notices
  1197. .ds [V 21
  1198. .ds [N 7
  1199. .nr [P 1
  1200. .ds [P 131-135
  1201. .ds [D 1986
  1202. .][
  1203. .[-
  1204. .ds [F Joh75
  1205. .ds [A S\*(p]\*(a]C\*(p] Johnson
  1206. .ds [T Yacc \(em  Yet Another Compiler-Compiler
  1207. .ds [R Computer Science Technical Report 32
  1208. .ds [I Bell Telephone Laboratories
  1209. .ds [C Murray Hill, NJ
  1210. .ds [D July 1975
  1211. .][
  1212. .[-
  1213. .ds [F KlM89
  1214. .ds [A E\*(p] Klein
  1215. .as [A \*(n]M\*(p] Martin
  1216. .ds [T The Parser Generating System PGS
  1217. .ds [J Software\(emPractice & Experience
  1218. .ds [V 19
  1219. .ds [N 11
  1220. .nr [P 1
  1221. .ds [P 1015-1028
  1222. .ds [D Nov. 1989
  1223. .][
  1224. .[-
  1225. .ds [F Les75
  1226. .ds [A M\*(p]\*(a]E\*(p] Lesk
  1227. .ds [T LEX \(em A Lexical Analyzer Generator
  1228. .ds [R Computing Science Technical Report 39
  1229. .ds [I Bell Telephone Laboratories
  1230. .ds [C Murray Hill, NJ
  1231. .ds [D 1975
  1232. .][
  1233. .[-
  1234. .ds [F Pax88
  1235. .ds [A V\*(p] Paxson
  1236. .ds [T Flex - Manual Pages
  1237. .ds [I Public Domain Software
  1238. .ds [D 1988
  1239. .][
  1240. .[-
  1241. .ds [F R\*oh76
  1242. .ds [A J\*(p] R\\*:ohrich
  1243. .ds [T Syntax-Error Recovery in LR-Parsers
  1244. .ds [E H\*(p] Schneider
  1245. .ds [E H.-J\*(p] Schneider
  1246. .as [E \*(n]M\*(p] Nagl
  1247. .nr [E 2
  1248. .ds [S Programmiersprachen, 4. Fachtagung der GI, Erlangen
  1249. .ds [B Informatik-Fachberichte
  1250. .ds [V 1
  1251. .nr [P 1
  1252. .ds [P 175-184
  1253. .ds [C Berlin
  1254. .ds [I Springer Verlag
  1255. .ds [D 1976
  1256. .][
  1257. .[-
  1258. .ds [F R\*oh80
  1259. .ds [A J\*(p] R\\*:ohrich
  1260. .ds [T Methods for the Automatic Construction of Error Correcting Parsers
  1261. .ds [J Acta Inf.
  1262. .ds [V 13
  1263. .ds [N 2
  1264. .nr [P 1
  1265. .ds [P 115-139
  1266. .ds [D 1980
  1267. .][
  1268. .[-
  1269. .ds [F R\*oh82
  1270. .ds [A J\*(p] R\\*:ohrich
  1271. .ds [T Behandlung syntaktischer Fehler
  1272. .ds [J Informatik Spektrum
  1273. .ds [V 5
  1274. .ds [N 3
  1275. .nr [P 1
  1276. .ds [P 171-184
  1277. .ds [D 1982
  1278. .][
  1279. .[-
  1280. .ds [F WaG84
  1281. .ds [A W\*(p]\*(a]M\*(p] Waite
  1282. .as [A \*(n]G\*(p] Goos
  1283. .ds [T Compiler Construction
  1284. .ds [I Springer Verlag
  1285. .ds [C New York, NY
  1286. .ds [D 1984
  1287. .][
  1288. .bp 1
  1289. .lp
  1290. .b Contents
  1291. .sp
  1292. .xp
  1293.